import time

num = 0
count = 16


def queen(A, current, H, X1, X2):
    global num
    if current == count:
        '''print(A)'''
        num = num + 1
    for i in range(0, len(A)):
        if H[i] == 0:
            if X1[current + i] == 0:
                if X2[current - i + count] == 0:
                    H[i] = 1
                    X1[current + i] = 1
                    X2[current - i + count] = 1
                    A[current] = i + 1
                    queen(A, current + 1, H, X1, X2)
                    X1[current + i] = 0
                    H[i] = 0
                    X2[current - i + count] = 0


def main():
    global num
    H = [0 for i in range(count)]
    X1 = [0 for i in range(count*2)]
    X2 = [0 for i in range(count*2)]
    print("十六皇后问题的所有解:")

    begin = time.perf_counter()
    queen([None] * count, 0, H, X1, X2)
    end = time.perf_counter()

    print("使用回溯法，十六皇后问题总共有%d种解" % num)
    print("运行时间为: %f" % (end - begin))


if __name__ == '__main__':
    main()
